package 布隆过滤器;

public class BloomFilter<T> {
	private int bitSize;	// 二进制位的个数
	private int hashSize;	// 哈希函数的个数
	private long[] bits;	// 二进制向量
	
	/**
	 * @param n	数据规模
	 * @param p	误判率
	 */
	public BloomFilter(int n, double p) {
		double ln2 = Math.log(2);
		
		bitSize = (int) (-n * Math.log(p) / Math.pow(ln2, 2));
		hashSize = (int) ((bitSize * ln2) / n);
		bits = new long[(bitSize + Long.SIZE - 1) / Long.SIZE];	// 与分页计算相同
	}
	
	/**
	 * @return	true: 修改过二进制向量
	 */
	public boolean put(T value) {
		valueNotNullCheck(value);
		// 根据value值, 通过不同的hash函数计算出不同的索引
		int hash1 = value.hashCode();
		int hash2 = hash1 >>> 16;
		boolean result = false;
		for (int i = 1; i <= hashSize; i++) {
			int combinedHash = hash1 + (i * hash2);
			if (combinedHash < 0) {
				combinedHash = ~combinedHash;
			} 
			// 生成一个二进位的索引
			int index = combinedHash % bitSize;
			// 将二进制向量中index位置的值设置为1
			if (set(index)) result = true;
		}
		return result;
	}
	
	public boolean contains(T value) {
		valueNotNullCheck(value);
		// 根据value值, 通过不同的hash函数计算出不同的索引
		int hash1 = value.hashCode();
		int hash2 = hash1 >>> 16;
	
		for (int i = 1; i <= hashSize; i++) {
			int combinedHash = hash1 + (i * hash2);
			if (combinedHash < 0) {
				combinedHash = ~combinedHash;
			} 
			// 生成一个二进位的索引
			int index = combinedHash % bitSize;
			// 将二进制向量中index位置的值设置为1
			if (!get(index)) return false;
		}
		return true;
	}
	
	private void valueNotNullCheck(T value) {
		if (value == null) throw new NullPointerException("Value cannot be null");
	}
	
	/**
	 * 设置index位置的值为1
	 */
	private boolean set(int index) {
		// 在long数组中找到对应的value值
		long value = bits[index / Long.SIZE];
		int bitValue = 1 << (index % Long.SIZE);
		bits[index / Long.SIZE] = value | bitValue;
		return (value & bitValue) == 0;
	}
	
	/**
	 * 查看index位置的值
	 * @return true: 1, false: 0
	 */
	private boolean get(int index) {
		long value = bits[index / Long.SIZE];
		int bitValue = 1 << (index % Long.SIZE);
		return (value & bitValue) != 0;
	}
	
	public static void main(String[] args) {
		BloomFilter<Integer> bf = new BloomFilter<>(1_0000_0000, 0.06);
		for (int i = 1; i <= 1_0000_0000; i++) {
			bf.put(i);
		}
		int count = 0;
		for (int i = 1_0000_0001; i <= 2_0000_0000; i++) {
			if (bf.contains(i)) {
				count++;
			}
		}
		System.out.println(count);
		
	}
}
